/**
//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 
//
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：[["a"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 回溯 👍 1089 👎 0

*/

package com.xixi.basicAlgroithms.backtracking;


import java.util.ArrayList;
import java.util.List;

public class ID00131PalindromePartitioning {
public static void main(String[] args)    {

    Solution solution = new ID00131PalindromePartitioning().new Solution();
    System.out.println(solution.partition("aabaa"));
}


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {

        char[] sChar = s.toCharArray();

        backTracking(sChar, sChar.length, 0, new ArrayList<>(), new ArrayList<>());

        return result;
    }



    public void backTracking(char[] sChar, int sLength, int index, List<Character> previousChars, List<String> path){

        if(index == sLength){ //最后一个字符串与前面的串组成了回文串
            return;
        }

        char nowChar = sChar[index];

        previousChars.add(nowChar);

        //#前一个串和当前字符，组成的是否是回文串，如果是，那下一个就可以割，不是，就不能割
        if(isPalindrome(previousChars)){ //如果是回文串，下一个字符和当前的隔开
            //当前字符与前一个串分割
            path.add(listToString(previousChars)); //当前串入path

            if(index == sLength - 1){
                result.add(new ArrayList<>(path)); //拍快照
                path.remove(path.size() -1); //当前串删除
                return; //后面就不用递了
            }

            backTracking(sChar,sLength, index + 1, new ArrayList<>(), path); //与前面切割

            path.remove(path.size() -1); //当前串删除


        }

        //当前串和下一个字符不切割，aaabaaa，递到最后才能判断是否是回文串
        backTracking(sChar,sLength, index + 1,  previousChars, path);
        previousChars.remove(previousChars.size() -1); //去掉当前字符

    }


    /*
     * @Desc: 判断回文串
     * @Author vincentML
     * @Date: 2022/4/21 13:54
 * @return boolean
    */
    public boolean isPalindrome(List<Character> previousChars){
        boolean isPal = true;

        for(int i = 0,j = previousChars.size() -1; i < j ; i++, j--){
            char pre = previousChars.get(i);
            char suf = previousChars.get(j);
            if(pre != suf){
                isPal = false;
                break;
            }

        }

        return isPal;
    }


    public String listToString(List<Character> previousChars){
        StringBuffer sb = new StringBuffer();
        for(Character c : previousChars){
            sb.append(c);
        }
        return sb.toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)




}